package org.leetcode.middle.leetcode213;

import java.util.Arrays;

public class Solution {
    public int rob(int[] nums) {

        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        //只需要考虑两种情况：1、第一个房间不偷；2、最后一个房间不偷
        return Math.max(robMax(nums, 0, n - 2), robMax(nums, 1, n - 1));
    }

    private int robMax(int[] nums, int start, int end) {

        int[] dp = new int[end - start + 1];

        if (start == end) {
            return nums[end];
        }

        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            dp[i-start] = Math.max(dp[i - start - 1], dp[i - start - 2] + nums[i]);
        }

        return dp[end-start];
    }

}
